package leetcode.editor.vip.solution1644;

import leetcode.editor.vip.solution1676.Solution1676;

public class Solution1644 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    boolean foundP = false, foundQ = false;

    // 参照labuladong：https://mp.weixin.qq.com/s/njl6nuid0aalZdH5tuDpqQ
    TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode node = find(root, p, q);
        if (!foundP || !foundQ) return null;
        return node;
    }

    public TreeNode find(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        TreeNode left = find(root.left, p, q);
        TreeNode right = find(root.right, p, q);

        if (left != null && right != null) {
            return root;
        }

        // 放在后边判断，防止p或者q不存在的情况
        // 注意放在 left != null && right != null 之后，处理left == null || right == null 的情况，此时才需要堆root进行判断
        if (root.val == p.val || root.val == q.val) {
            if (root.val == p.val) foundP = true;
            if (root.val == q.val) foundQ = true;
            // 直接返回，因为是后序处理，可以不用管
            return root;
        }

        return left == null ? right : left;
    }
}
